package sort;

/**
 * 快速排序
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 5, 2, 5};
        QuickSort2 qq = new QuickSort2();
        qq.quickSort(nums);
        System.out.println(1);
    }


    public void quickSort(int[] nums){
        sort(nums,0,nums.length - 1);
    }

    public void sort(int[] nums,int start,int end){
        if(start >= end){
            return;
        }
        int mid = partition(nums,start,end);
        if(mid == -1){
            return;
        }
        sort(nums,start,mid - 1);
        sort(nums,mid + 1,end);
    }

    public int partition(int[] nums,int left, int right){
        if(left > right) return -1;
        int base = nums[left];
        int i = left + 1;
        int j = right;
        while (i < j){
            while (i < j && nums[j] >= base){
                j--;
            }
            while (i < j && nums[i] < base){
                i++;
            }
            if(i < j){
                swap(nums,i,j);
            }
        }
        swap(nums,left,i);
        return i;
    }

    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }



}
